#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

/**
  * @方法: 滑动窗口
  * @时间复杂度: o(n)
  * @空间复杂度: o(|z|)，|z|是字符集大小
  * @评价: 官方解法，学习使用滑动窗口
*/
int lengthOfLongestSubstring(string s) {
    int ans = 0;
    int n = s.length();
    unordered_set<char> tag;
    int right = 0;
    for (int i = 0; i < n; i++) {
        if (i != 0) {
            tag.erase(s[i - 1]);
        }
        while (!tag.count(s[right]) && right < n) {
            tag.insert(s[right]);
            right++;
        }
        ans = max(ans, right - i);
    }
    return ans;
}

/**
 * @方法: 双重循环、剪枝
 * @时间复杂度: o(n^2)
 * @空间复杂度: o(n)
 * @评价: 自建查找为o(1)的哈希
 */
int lengthOfLongestSubstring1(string s) {
    int ans = 0;
    int n = s.length();
    for (int i = 0; i < n; i++) {
        if (n - i <= ans) {
            break;
        }
        int tag[10000] = {};
        int j;
        for (j = i; j < n; j++) {
            if (tag[(int)s[j]] == 1) {
                break;
            } else {
                tag[(int)s[j]] = 1;
            }
        }
        if (j == n)
            ans = max(ans, n - i);
        else
            ans = max(ans, j - i);
    }
    return ans;
}


int main() {

    cout << "hello world" << endl;

    return 0;
}